package 剑指offer;

/**
 * 构建乘积数组
 * https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/solution/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/
 */
public class Offer66_JZ51 {
    public int[] constructArr(int[] a) {
        int[] res = new int[a.length];
        for (int i=0; i<a.length; i++) {
            int sum = 1;
            for (int j=0; j<a.length; j++) {
                if (j != i)
                    sum *= a[j];
            }
            res[i] = sum;
        }
        return res;
    }

    public int[] constructArr2(int[] a) {
        int n = a.length;
        int[] b = new int[n];
        if (n == 0) {
            return b;
        }
        b[0] = 1;
        int temp = 1;
        for (int i=1; i<n; i++) {
            b[i] = b[i-1] * a[i-1];
        }
        for (int i=n-2; i>=0; i--) {
            temp *= a[i+1];
            b[i] *= temp;
        }
        return b;
    }
}
